package DP.子序列.回文问题;

import org.junit.Test;

/*
    因为res要具体str -> 只能用背的扩散法
    要不可以用 外staticmax+内cur保证相连 后序找出最长长度int
*/
public class 回文子串_要背的_扩散法_5 {
    @Test
    public void test() {
        System.out.println(longestPalindrome("cbbd"));
    }

    /*
        试一下 干中[单] 板子解决迭代for问题 可行不？ 、
        -> 不可行，但中间‘单迭’不变

        倒序终点开始 or 正序起点到终点 ？
        -> 正序（普通人思维）
    */
    char[] s; int n;
    int maxLen = 0;
    int[] resIJ = new int[2];
    public String longestPalindrome(String t) {
        s = t.toCharArray(); n = t.length();
        for (int i = 0; i < n; i++) {
            //奇 - 单个为起点（注：起点不是cur，cur是ij2个组合）
            int start = i;
            maxOfIJ_danqidian(start);
            System.out.println(String.format("%s", t.substring(resIJ[0],resIJ[1]+1)));
            //偶 - 2个相同的为起点【不相同的不能当起点，会错误更新maxStr】
            int start1=i,start2=i+1;
            if(start2<n && s[start1]==s[start2]) {
                maxOfIJ_shuangqidian(start1, start2);
            }
        }
        return t.substring(resIJ[0],resIJ[1]+1);
    }
    public void maxOfIJ_danqidian(int sI){
        int l=sI-1, r=sI+1;
        while(l>=0 && r<n){
            if(s[l] == s[r]){
                if(r-l>maxLen){
                    maxLen = r-l;
                    resIJ[0]=l;resIJ[1]=r;
                }
                //迭代别少
                l--;r++;
            }
            else if(s[l] != s[r]){
                //立即终止
                break;
            }
        }
    }
    private void maxOfIJ_shuangqidian(int start1, int start2) {
        //cbbd：里面bb=2没统计
        if(maxLen<2-1){
            maxLen=2-1;
            resIJ[0]=start1;resIJ[1]=start2;
        }

        int l=start1-1, r=start2+1;
        while(l>=0 && r<n){
            if(s[l] == s[r]){
                if(r-l>maxLen){
                    maxLen = r-l;
                    resIJ[0]=l;resIJ[1]=r;
                }
                l--;r++;
            }
            else if(s[l] != s[r]){
                break;
            }
        }
    }
}
